package algotithm.leetcode.listnode.test148;

import algotithm.leetcode.listnode.ListNode;

/**
 * @author zhouyanxiang
 * @Date 2021-02-2021/2/18-9:36
 * @URL https://leetcode-cn.com/problems/sort-list/
 * @Title 148. 排序链表
 */
public class Solution {

    public static void main(String[] args) {
        ListNode head = new ListNode(-1);
        ListNode t1 = new ListNode(5);
        ListNode t2 = new ListNode(3);
        ListNode t3 = new ListNode(4);
        ListNode t4 = new ListNode(0);

        head.next = t1;
        t1.next = t2;
        t2.next = t3;
        t3.next = t4;
        t4.next = null;

        Solution solution = new Solution();
        ListNode listNode = solution.sortList(head);
        while (listNode != null) {
            System.out.print(listNode.val + " ");
            listNode = listNode.next;
        }
    }

    public ListNode sortList(ListNode head) {
        if (head == null || head.next == null) {
            return head;
        }
        ListNode fast = head.next;
        ListNode slow = head;
        while (fast != null && fast.next != null) {
            fast = fast.next.next;
            slow = slow.next;
        }
        ListNode tmp = slow.next;
        slow.next = null;
        ListNode l = sortList(head);
        ListNode r = sortList(tmp);
        ListNode dummy = new ListNode(0);
        dummy.next = l;
        ListNode test = dummy;
        while (l != null && r != null) {
            if (l.val  <= r.val) {
                test.next = l;
                l = l.next;
            } else {
                test.next = r;
                r = r.next;
            }
            test = test.next;
        }
        test.next = l != null ? l : r;
        return dummy.next;

    }

}
